package com.yuanzhi.train;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * @author yuanZhi
 * @since 2021/5/19 13:43
 */
public class LevelOrder {
	static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	public static void main(String[] args) {
		TreeNode treeNode = new TreeNode(3, new TreeNode(9, null, null),
				new TreeNode(20, new TreeNode(15, null, null),
						new TreeNode(7, null, null)));
		List<List<Integer>> lists = levelOrder(treeNode);
		System.out.println(lists);

		TreeNode treeNode1 = new TreeNode(1,
				new TreeNode(2, new TreeNode(4, null, null), null),
				new TreeNode(3, null, new TreeNode(5, null, null)));
		List<List<Integer>> lists1 = levelOrder(treeNode1);
		System.out.println(lists1);
	}

	public static List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> result = new ArrayList<>();
		if (Objects.isNull(root)) {
			return result;
		}
		recursive(result, root, 0);
		return result;
	}

	public static void recursive(List<List<Integer>> result, TreeNode root,
			int level) {
		if (result.size() == level) {
			result.add(new ArrayList<>());
		}
		// 需要获取其他节点相同层级的，所以不可以直接创建
		result.get(level).add(root.val);
		if (Objects.nonNull(root.left)) {
			recursive(result, root.left, level + 1);
		}
		if (Objects.nonNull(root.right)) {
			recursive(result, root.right, level + 1);
		}
	}
}
